package com.leetcode.leetcode.anyan;

import java.util.HashSet;
import java.util.Set;

public class _面试题_02_01移除重复节点 {
    /**
     * 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
     *
     * 示例1:
     *
     *  输入：[1, 2, 3, 3, 2, 1]
     *  输出：[1, 2, 3]
     * 示例2:
     *
     *  输入：[1, 1, 1, 1, 2]
     *  输出：[1, 2]
     * 提示：
     *
     * 链表长度在[0, 20000]范围内。
     * 链表元素在[0, 20000]范围内。
     * 进阶：
     *
     * 如果不得使用临时缓冲区，该怎么解决？
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */


      public static class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
      }
    static class Solution {
        public static ListNode removeDuplicateNodes(ListNode head) {
            if (head == null) {
                return head;
            }
            ListNode pos = head;
            Set<Integer> s = new HashSet<Integer>();
            s.add(pos.val);
            while(pos.next != null) {
                ListNode cur = pos.next;
                if (s.add(cur.val)) {
                    pos = pos.next;
                } else {
                    pos.next = pos.next.next;
                }
            }
            return head;
        }

        public static void main(String[] args) {
            ListNode cur = new ListNode(1);
            ListNode node = cur;
            node.next = new ListNode(2);
            node = node.next;
            node.next = new ListNode(3);
            node = node.next;
            node.next = new ListNode(3);
            node = node.next;
            node.next = new ListNode(2);
            node = node.next;
            node.next = new ListNode(1);
            node = node.next;
            node.next = new ListNode(8);
            ListNode re = removeDuplicateNodes(cur);
            System.out.println(re.val);
            while (re.next != null) {
                System.out.println(re.next.val);
                re = re.next;
            }
        }
    }
}
